// 题目描述
// 95. 不同的二叉搜索树 II
// 难度
// 中等
// 1443
// 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
//   示例 1：
// 输入：n = 3
// 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
// 示例 2：
// 输入：n = 1
// 输出：[[1]]
//   提示：
// 1 <= n <= 8
// 通过次数170,673提交次数232,464

function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  let ans = null

  const helper = (l, r) => {
    const res = []

    if (l > r) {
      // 这种情况，返回结果一定要加入一个 null
      // 因为 null 本质上是一个空节点，代表了子节点为空的一大类情况
      res.push(null)
      return res
    }

    for (let i = l; i <= r; i++) {
      // 左子树情况
      const lChildRes = helper(l, i - 1)
      // 右子树情况
      const rChildRes = helper(i + 1, r)

      // 左子树右子树各选一个，拼接所有情况
      for (const lChild of lChildRes) {
        for (const rChild of rChildRes) {
          const root = new TreeNode(i, lChild, rChild)
          res.push(root)
        }
      }
    }

    return res
  }
  ans = helper(1, n)

  return ans
}


const res = generateTrees(3)
